{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Wonderful Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #hash-table #string #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #哈希表 #字符串 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wonderfulSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最美子字符串的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果某个字符串中 <strong>至多一个</strong> 字母出现 <strong>奇数</strong> 次，则称其为 <strong>最美</strong> 字符串。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"ccjjc\"</code> 和 <code>\"abab\"</code> 都是最美字符串，但 <code>\"ab\"</code> 不是。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串 <code>word</code> ，该字符串由前十个小写英文字母组成（<code>'a'</code> 到 <code>'j'</code>）。请你返回 <code>word</code> 中 <strong>最美非空子字符串</strong> 的数目<em>。</em>如果同样的子字符串在<em> </em><code>word</code> 中出现多次，那么应当对 <strong>每次出现</strong> 分别计数<em>。</em></p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是字符串中的一个连续字符序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"aba\"\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>4 个最美子字符串如下所示：\n",
    "- \"<strong>a</strong>ba\" -> \"a\"\n",
    "- \"a<strong>b</strong>a\" -> \"b\"\n",
    "- \"ab<strong>a</strong>\" -> \"a\"\n",
    "- \"<strong>aba</strong>\" -> \"aba\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"aabb\"\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>9 个最美子字符串如下所示：\n",
    "- \"<strong>a</strong>abb\" -> \"a\"\n",
    "- \"<strong>aa</strong>bb\" -> \"aa\"\n",
    "- \"<strong>aab</strong>b\" -> \"aab\"\n",
    "- \"<strong>aabb</strong>\" -> \"aabb\"\n",
    "- \"a<strong>a</strong>bb\" -> \"a\"\n",
    "- \"a<strong>abb</strong>\" -> \"abb\"\n",
    "- \"aa<strong>b</strong>b\" -> \"b\"\n",
    "- \"aa<strong>bb</strong>\" -> \"bb\"\n",
    "- \"aab<strong>b</strong>\" -> \"b\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"he\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>2 个最美子字符串如下所示：\n",
    "- \"<b>h</b>e\" -> \"h\"\n",
    "- \"h<strong>e</strong>\" -> \"e\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= word.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>word</code> 由从 <code>'a'</code> 到 <code>'j'</code> 的小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-wonderful-substrings](https://leetcode.cn/problems/number-of-wonderful-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-wonderful-substrings](https://leetcode.cn/problems/number-of-wonderful-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aba\"', '\"aabb\"', '\"he\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "\n",
    "        cnt = [0] * 1024\n",
    "        cnt[0] = 1\n",
    "        cur = ans = 0\n",
    "        for s in word:\n",
    "            cur ^= 1 << (ord(s) - ord('a'))\n",
    "            ans += cnt[cur]\n",
    "            for i in range(10):\n",
    "                ans += cnt[cur ^ (1 << i)]\n",
    "            cnt[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        cnt = Counter()\n",
    "        cnt[0] = 1\n",
    "        ans = mask = 0\n",
    "        for c in word:\n",
    "            mask ^= 1 << (ord(c) - 97)\n",
    "            ans += cnt[mask]\n",
    "            for i in range(10):\n",
    "                ans += cnt[mask ^ (1 << i)]\n",
    "            cnt[mask] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        cnt = [0] * 1024\n",
    "        cnt[0] = 1  # 初始前缀和为 0，需将其计入出现次数\n",
    "        ans = s = 0\n",
    "        for c in word:\n",
    "            s ^= 1 << (ord(c) - ord('a'))  # 计算当前前缀和\n",
    "            ans += cnt[s]  # 所有字母均出现偶数次\n",
    "            ans += sum(cnt[s ^ (1 << i)] for i in range(10))  # 枚举其中一个字母出现奇数次，反转该字母的出现次数的奇偶性\n",
    "            cnt[s] += 1  # 更新前缀和出现次数\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        cnt = [0] * 1024\n",
    "        cnt[0] = 1\n",
    "        ans = s = 0\n",
    "        for c in word:\n",
    "            s ^= 1 << (ord(c) - ord('a'))\n",
    "            ans += cnt[s]\n",
    "            ans += sum(cnt[s ^ (1 << i)] for i in range(10))\n",
    "            cnt[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        mapping = {0:1}\n",
    "        result = 0\n",
    "        bit = 0\n",
    "        for c in word:\n",
    "            bit = bit ^ (1<<(ord(c)-ord('a')))\n",
    "            if(bit in mapping):\n",
    "                result += mapping[bit]\n",
    "            for i in range(10):\n",
    "                bit_copy = bit ^ (1<<i)\n",
    "                if(bit_copy in mapping):\n",
    "                    result += mapping[bit_copy]\n",
    "            if(bit not in mapping):\n",
    "                mapping[bit] = 1\n",
    "            else:\n",
    "                mapping[bit] += 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        mask, ans = 0, 0\n",
    "        mp = defaultdict(int)\n",
    "        mp[0] = 1\n",
    "        for i, c in enumerate(word):\n",
    "            x = ord(c) - ord('a')\n",
    "            mask ^= 1 << x\n",
    "            ans += mp[mask]\n",
    "            for j in range(0, 10):\n",
    "                t = mask ^ (1 << j)\n",
    "                if t in mp:\n",
    "                    ans += mp[t]\n",
    "            mp[mask] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        count = 0\n",
    "        freq = [0] * 1024\n",
    "        freq[0] = 1\n",
    "        bitmask = 0\n",
    "        for char in word:\n",
    "            bitmask ^= 1 << (ord(char) - ord('a'))\n",
    "            count += freq[bitmask]\n",
    "            for i in range(10):\n",
    "                count += freq[bitmask ^ (1 << i)]\n",
    "            freq[bitmask] += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        cnt = Counter()\n",
    "        cnt[0] += 1\n",
    "        ans = 0\n",
    "        state = 0\n",
    "\n",
    "        for ch in word:\n",
    "            state ^= 1 << (ord(ch) - ord('a'))\n",
    "            ans += cnt[state]\n",
    "            ans += sum(cnt[state ^ (1 << i)] for i in range(10))\n",
    "            cnt[state] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        count = [0] * 1024\n",
    "        count[0] = 1\n",
    "        ans = 0\n",
    "        sum = 0\n",
    "        for i in range(len(word)):\n",
    "            sum ^= 1 << (ord(word[i]) - ord('a'))\n",
    "            ans += count[sum]\n",
    "            for i in range(10):\n",
    "                ans += count[sum ^ (1 << i)]\n",
    "            count[sum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        d=defaultdict(int)\n",
    "        d[0]=1\n",
    "        res=pre=0\n",
    "        for c in word:\n",
    "            pre^=1<<(ord(c)-ord(\"a\"))\n",
    "            res+=d[pre]\n",
    "            for i in range(10):\n",
    "                res+=d[pre^(1<<i)]\n",
    "            d[pre]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        aux = Counter()\n",
    "        aux[0] = 1\n",
    "        get_n = lambda x: ord(x) - ord('a')\n",
    "        rs = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            rs ^= 1<<get_n(ch)\n",
    "            r  = i+1\n",
    "            if rs in aux:\n",
    "                ans +=  aux[rs]\n",
    "            for k in range(10):    \n",
    "                if rs ^ (1<<k) in aux:\n",
    "                    ans +=  aux[rs^(1<<k)]\n",
    "                \n",
    "            aux[rs] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        cnt = [0] * 1024\n",
    "        cnt[0] = 1  # 初始前缀和为 0，需将其计入出现次数\n",
    "        ans = s = 0\n",
    "        for c in word:\n",
    "            s ^= 1 << (ord(c) - ord('a'))  # 计算当前前缀和\n",
    "            ans += cnt[s]  # 所有字母均出现偶数次\n",
    "            ans += sum(cnt[s ^ (1 << i)] for i in range(10))  # 枚举其中一个字母出现奇数次，反转该字母的出现次数的奇偶性\n",
    "            cnt[s] += 1  # 更新前缀和出现次数\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        mp = {0: 1}\n",
    "        res = 0\n",
    "        n = len(word)\n",
    "        state = 0\n",
    "        for i in range(n):\n",
    "            state ^= (1 << (ord(word[i]) - ord('a')))\n",
    "            res += mp.get(state, 0)\n",
    "            for j in range(10):\n",
    "                res += mp.get(state ^ (1 << j), 0)\n",
    "            mp[state] = mp.get(state, 0) + 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "\n",
    "        mask=0\n",
    "        cnt=Counter()\n",
    "        cnt[0]=1\n",
    "        res=0\n",
    "        for i,v in enumerate(word):\n",
    "            mask^=1<<(ord(v)-97)\n",
    "            res+=cnt[mask]\n",
    "            for j in range(26):\n",
    "                res+=cnt[mask^(1<<j)]\n",
    "            cnt[mask]+=1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        mask, ans = 0, 0\n",
    "        mp = defaultdict(int)\n",
    "        mp[0] = 1\n",
    "        for i, c in enumerate(word):\n",
    "            x = ord(c) - ord('a')\n",
    "            mask ^= 1 << x\n",
    "            ans += mp[mask]\n",
    "            for j in range(0, 26):\n",
    "                t = mask ^ (1 << j)\n",
    "                if t in mp:\n",
    "                    ans += mp[t]\n",
    "            mp[mask] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        cnt = defaultdict(int)\n",
    "        cnt[0] = 1\n",
    "        pre = 0\n",
    "        for c in word:\n",
    "            pre ^= 1 << (ord(c) - ord('a'))\n",
    "            ans += cnt[pre]\n",
    "            for i in range(10):\n",
    "                ans += cnt[pre ^ (1 << i)]\n",
    "            cnt[pre] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        aux = Counter([0])\n",
    "        n = len(word)\n",
    "        get_n = lambda x : ord(x) - ord('a')\n",
    "        ps = 0\n",
    "        ans = 0\n",
    "        for r,ch in enumerate(word):\n",
    "            ps = ps ^ (1<<get_n(ch))\n",
    "            ans += aux[ps]\n",
    "            for k in range(10):\n",
    "                ans += aux[ps ^(1<<k)]\n",
    "            aux[ps] +=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        cnt = [0] * 1024\n",
    "        cnt[0] = 1  # 初始前缀和为 0，需将其计入出现次数\n",
    "        ans = s = 0\n",
    "        for c in word:\n",
    "            s ^= 1 << (ord(c) - ord('a'))  # 计算当前前缀和\n",
    "            ans += cnt[s]  # 所有字母均出现偶数次\n",
    "            ans += sum(cnt[s ^ (1 << i)] for i in range(10))  # 枚举其中一个字母出现奇数次，反转该字母的出现次数的奇偶性\n",
    "            cnt[s] += 1  # 更新前缀和出现次数\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "al = 'abcdefjhij'\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        m = defaultdict(int)\n",
    "        m[0] = 1\n",
    "        cur = ans = 0\n",
    "        # 一个奇数次的字符\n",
    "        for c in word:\n",
    "            cur ^= 1 << (ord(c) - ord('a'))\n",
    "            ans += m[cur]\n",
    "            for i in range(10):\n",
    "                ans += m[cur ^ (1 << i)]\n",
    "            m[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        res = 0\n",
    "        n = len(word)\n",
    "        cnt = [0] * 1024\n",
    "        cnt[0] = 1  # 初始前缀和为 0，需将其计入出现次数\n",
    "        dt = {0:-1}\n",
    "        pattern = 0\n",
    "        for idx, w in enumerate(word):\n",
    "            bit = 1 << (ord(w) - ord('a'))\n",
    "            pattern ^= bit\n",
    "            res += cnt[pattern]\n",
    "\n",
    "            res += sum(cnt[pattern^(1<<i)] for i in range(10))\n",
    "\n",
    "            cnt[pattern] += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        dp = [1] * n\n",
    "\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "\n",
    "        cnt = Counter([0])\n",
    "        cur = ans = 0\n",
    "        for s in word:\n",
    "\n",
    "            cur ^= 1 << (ord(s) - ord('a'))\n",
    "            ans += cnt[cur]\n",
    "            for i in range(26):\n",
    "                ans += cnt[cur ^ (1 << i)]\n",
    "            cnt[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        pre, res = 0, 0\n",
    "        freq = {0:1}\n",
    "        for ch in word:\n",
    "            x = ord(ch) - ord('a')\n",
    "            pre ^= (1 << x)\n",
    "            res += freq.get(pre, 0)\n",
    "            for i in range(10):\n",
    "                also = pre ^ (1 << i)\n",
    "                res += freq.get(also, 0)\n",
    "            freq[pre] = freq.get(pre, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        freq = Counter([0])\n",
    "        mask, ans = 0, 0\n",
    "        \n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            mask ^= (1 << idx)\n",
    "            if mask in freq:\n",
    "                ans += freq[mask]\n",
    "            for i in range(10):\n",
    "                if (mask_pre := mask ^ (1 << i)) in freq:\n",
    "                    ans += freq[mask_pre]\n",
    "            freq[mask] += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        pre = 0\n",
    "        pre2con = {} # key:前缀字母奇偶数，value:前缀字母奇偶数总前缀数\n",
    "        pre2con[0] = 1 # 初始化，前缀一个字母都没有时\n",
    "        res = 0\n",
    "\n",
    "        for c in word:\n",
    "            pre ^= (1 << (ord(c) - ord(\"a\")))\n",
    "            res += pre2con.get(pre, 0) # 全是偶数，全部相同\n",
    "            for i in range(10): # 包含一个奇数，因此有一个不同\n",
    "                res += pre2con.get(pre ^ (1 << i), 0)\n",
    "            pre2con[pre] = pre2con.get(pre, 0) + 1\n",
    "\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        count = [0] * 1024  # 计数数组，用于记录每个前缀的奇数字符出现次数的状态\n",
    "        count[0] = 1  # 空字符串的状态为0\n",
    "        mask = 0  # 当前前缀的状态\n",
    "\n",
    "        result = 0\n",
    "\n",
    "        for char in word:\n",
    "            # 计算当前字符对应的二进制位\n",
    "            bit = ord(char) - ord('a')\n",
    "\n",
    "            # 更新当前前缀的状态\n",
    "            mask ^= 1 << bit\n",
    "\n",
    "            # 计算与当前前缀状态相差一个字符的状态\n",
    "            result += count[mask]\n",
    "\n",
    "            # 计算与当前前缀状态相差一个字符的状态（每个字符出现偶数次）\n",
    "            for i in range(10):\n",
    "                result += count[mask ^ (1 << i)]\n",
    "\n",
    "            # 更新计数数组\n",
    "            count[mask] += 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        d = [0] * 1111\n",
    "        num, d[0], ret = 0, 1, 0\n",
    "        for i in word:\n",
    "            id = ord(i) - ord('a')\n",
    "            num ^= (1 << id)\n",
    "            ret += d[num]\n",
    "            for j in range(10):\n",
    "                ret += d[num ^ (1 << j)]\n",
    "            d[num] += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        freq = Counter([0])\n",
    "        mask, ans = 0, 0\n",
    "        \n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            mask ^= (1 << idx)\n",
    "            if mask in freq:\n",
    "                ans += freq[mask]\n",
    "            for i in range(10):\n",
    "                mask_pre = mask ^ (1 << i)\n",
    "                if (mask_pre := mask ^ (1 << i)) in freq:\n",
    "                    ans += freq[mask_pre]\n",
    "            freq[mask] += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "\n",
    "        freq = Counter([0])\n",
    "        mask, res = 0, 0\n",
    "\n",
    "\n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "\n",
    "            mask ^= (1 << idx)\n",
    "            if mask in freq:\n",
    "                res += freq[mask]\n",
    "            for i in range(10):\n",
    "                mask_pre = mask ^ (1 << i)\n",
    "                if mask_pre in freq:\n",
    "                    res += freq[mask_pre]\n",
    "\n",
    "            freq[mask] += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "\n",
    "        cnt = Counter([0])\n",
    "        cur = ans = 0\n",
    "        for s in word:\n",
    "            cur ^= 1 << (ord(s) - ord('a'))\n",
    "            ans += cnt[cur]\n",
    "            for i in range(10):\n",
    "                ans += cnt[cur ^ (1 << i)]\n",
    "            cnt[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        freq = Counter([0])\n",
    "        mask, res = 0, 0\n",
    "\n",
    "\n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "\n",
    "            mask ^= (1 << idx)\n",
    "            if mask in freq:\n",
    "                res += freq[mask]\n",
    "            for i in range(10):\n",
    "                mask_pre = mask ^ (1 << i)\n",
    "                if mask_pre in freq:\n",
    "                    res += freq[mask_pre]\n",
    "\n",
    "            freq[mask] += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        record = collections.defaultdict(int)\n",
    "        record[0] = 1\n",
    "        mask, res = 0, 0\n",
    "        for i in range(n):\n",
    "            index = ord(word[i]) - ord('a')\n",
    "            mask ^= (1<<index)\n",
    "            if mask in record:\n",
    "                res += record[mask]\n",
    "            for j in range(10):\n",
    "                mask_pre = mask^(1<<j)\n",
    "                res += record[mask_pre]\n",
    "            record[mask] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        def f(c):\n",
    "            return 1 << (ord(c) - ord('a'))\n",
    "        n = len(word)\n",
    "        mp = defaultdict(int)\n",
    "        mp[0] += 1\n",
    "        ans = mask = 0\n",
    "        for i in range(n):\n",
    "            mask ^= f(word[i])\n",
    "            for j in range(10):\n",
    "                ans += mp[mask ^ (1 << j)]\n",
    "            ans += mp[mask]\n",
    "            mp[mask] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        count = {0: 1}  # 初始化前缀和哈希表，什么都没有时，对应的状态是0\n",
    "        state = 0  # 初始状态也是0\n",
    "        ans = 0  # 存储最终答案\n",
    "        \n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord('a')  # 计算字符对应的索引\n",
    "            state ^= (1 << idx)  # 更新状态\n",
    "            \n",
    "            # 如果这个状态出现过，那么从之前的状态到当前状态的子串满足条件\n",
    "            ans += count.get(state, 0)\n",
    "            \n",
    "            # 检查只有一个字符出现奇数次的所有可能状态\n",
    "            for i in range(10):\n",
    "                tmp = state ^ (1 << i)\n",
    "                ans += count.get(tmp, 0)\n",
    "                \n",
    "            # 更新前缀和哈希表\n",
    "            count[state] = count.get(state, 0) + 1\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        freq = Counter([0])\n",
    "        mask, res = 0, 0\n",
    "\n",
    "\n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "\n",
    "            mask ^= (1 << idx)\n",
    "            if mask in freq:\n",
    "                res += freq[mask]\n",
    "            for i in range(10):\n",
    "                mask_pre = mask ^ (1 << i)\n",
    "                if (mask_pre := mask ^ (1 << i )) in freq:\n",
    "                    res += freq[mask_pre]\n",
    "\n",
    "            freq[mask] += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        d={0:1}\n",
    "        presum=0\n",
    "        ans=0\n",
    "        for i,x in enumerate(word):\n",
    "            presum^=(1<<ord(x)-ord('a'))\n",
    "            for i in range(10):\n",
    "                cur=presum ^ (1<<i)\n",
    "                if cur in d:\n",
    "                    ans+=d[cur]\n",
    "\n",
    "            if presum in d:\n",
    "                ans+=d[presum]\n",
    "                d[presum]+=1\n",
    "            else:\n",
    "                d[presum]=1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        def f(c):\n",
    "            return 1 << (ord(c) - ord('a'))\n",
    "        n = len(word)\n",
    "        mp = Counter()\n",
    "        mp[0] += 1\n",
    "        ans = mask = 0\n",
    "        for i in range(n):\n",
    "            mask ^= f(word[i])\n",
    "            for j in range(10):\n",
    "                ans += mp[mask ^ (1 << j)]\n",
    "            ans += mp[mask]\n",
    "            mp[mask] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        cnts = Counter()\n",
    "        cnts[0] = 1\n",
    "        cur = 0\n",
    "        for i , w in enumerate(word):\n",
    "            cur ^= 1 << (ord(w) - ord('a'))\n",
    "            ans += cnts[cur]\n",
    "            for j in range(26):\n",
    "                ans += cnts[cur ^ (1 << j)]\n",
    "            cnts[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        freq = Counter([0])\n",
    "        mask, ans = 0, 0\n",
    "        \n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            mask ^= (1 << idx)\n",
    "            if mask in freq:\n",
    "                ans += freq[mask]\n",
    "            for i in range(10):\n",
    "                if (mask_pre := mask ^ (1 << i)) in freq:\n",
    "                    ans += freq[mask_pre]\n",
    "            freq[mask] += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        freq = Counter([0])\n",
    "        mask, ans = 0, 0\n",
    "        \n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            mask ^= (1 << idx)\n",
    "            if mask in freq:\n",
    "                ans += freq[mask]\n",
    "            for i in range(10):\n",
    "                mask_pre = mask ^ (1 << i)\n",
    "                if (mask_pre := mask ^ (1 << i)) in freq:\n",
    "                    ans += freq[mask_pre]\n",
    "            freq[mask] += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        get_n = lambda ch:ord(ch) - ord('a')\n",
    "        rs = 0\n",
    "        # P[r+1] ^ P[l]  = 0\n",
    "        # P[r+1] ^ P[l] = x   where x.bit_count() ==1\n",
    "        aux = Counter([0])\n",
    "        ans = 0\n",
    "        for ch in word:\n",
    "            rs = rs ^ (1<<get_n(ch))\n",
    "            ans += aux[rs]\n",
    "            for k in range(10):\n",
    "                ans += aux[rs ^(1<<k)]\n",
    "                \n",
    "            aux[rs]+= 1\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        word_freq = {}\n",
    "        word_freq[0] = 1\n",
    "        mask, res = 0, 0\n",
    "        for c in word:\n",
    "            mask ^= 1 << ord(c) - ord('a')\n",
    "            if mask in word_freq:\n",
    "                res += word_freq[mask]\n",
    "            for i in range(10):\n",
    "                mask1 = mask ^ (1 << i)\n",
    "                if mask1 in word_freq:\n",
    "                    res += word_freq[mask1]\n",
    "            if mask in word_freq:\n",
    "                word_freq[mask] += 1\n",
    "            else:\n",
    "                word_freq[mask] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        d={0:1}\n",
    "        presum=0\n",
    "        ans=0\n",
    "        for i,x in enumerate(word):\n",
    "            presum^=(1<<ord(x)-ord('a'))\n",
    "            for i in range(26):\n",
    "                cur=presum ^ (1<<i)\n",
    "                if cur in d:\n",
    "                    ans+=d[cur]\n",
    "\n",
    "            if presum in d:\n",
    "                ans+=d[presum]\n",
    "                d[presum]+=1\n",
    "            else:\n",
    "                d[presum]=1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "al = 'abcdefghij'\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        m = defaultdict(int)\n",
    "        m[0] = 1\n",
    "        cur = ans = 0\n",
    "        for c in word:\n",
    "            cur ^= 1 << (ord(c) - ord('a'))\n",
    "            ans += m[cur]\n",
    "            for nex in al:\n",
    "                tar = cur ^ (1 << (ord(nex) - ord('a')))\n",
    "                ans += m[tar]\n",
    "            m[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wonderfulSubstrings(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        pre = defaultdict(int)\n",
    "        state = 0\n",
    "        pre[state] = 1\n",
    "        target = [1<<i for i in range(26)]\n",
    "        for w in word:\n",
    "            state ^= (1<<(ord(w)-ord(\"a\")))\n",
    "            ans += sum(pre[state^x] for x in target)\n",
    "            ans += pre[state]\n",
    "            pre[state] += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
